perm filename READIN[BOO,JMC] blob
sn#762067 filedate 1984-07-03 generic text, type C, neo UTF8
COMMENT ⊗ VALID 00018 PAGES
C REC PAGE DESCRIPTION
C00001 00001
C00003 00002 .if false then begin "questions"
C00005 00003 .s(READIN,INTRODUCTION TO LISP)
C00007 00004 .ss(lists,Lists.)
C00013 00005 .ss(atoms,Atoms.)
C00015 00006 .ss(liststruc,List structures.)
C00022 00007 .ss(sexp, S-expressions.)
C00033 00008 .ss(basicfns, The basic functions and predicates on S-expressions.)
C00054 00009 .ss(cond,Conditional terms.)
C00063 00010 .ss(andor,Propositional terms.)
C00069 00011 .ss(recdefn,Recursive function definitions.)
C00089 00012 .ss(numbers,Numerical computation.)
C00101 00013 .ss(bool,Bitwise Boolean Operations)
C00107 00014 .ss(lambda,Lambda expressions and functions with functions as arguments.)
C00121 00015 .ss(alpha,Label.)
C00124 00016 .if false then begin "hide Park comment"
C00125 00017 .ss(evaluator,The function eval. )
C00144 00018 .if false then begin "hide eval exercises"
C00145 ENDMK
C⊗;
.if false then begin "questions"
should it be made more clear from the beginning that the character
strings discussed are a particular notation for S-expressions
and not themselves S-expressions?
.ss(liststruc,List structures.) is the use of "/3" confusing?
when TEXed make it look better
in describing list structures perhaps the term "cons cell" should
be used and explained as pair of cells each of which could be a word or half word.
discussion of qT representing qtrue in last paragraph of section on conditionals
should be fixed. remove ref to basic section and possibly move to sections
on propops
.end "questions"
.s(READIN,INTRODUCTION TO LISP)
.if NOTASSEMBLING then start
.WRITIN: NEXT SECTION!;
.PROVIN: NEXT SECTION!;
.PROVEX: NEXT SECTION!;
.IMPURE: NEXT SECTION!;
.MACHIN: NEXT SECTION!;
.SEARCH: NEXT SECTION!;
.EXTEND: NEXT SECTION!;
.ABSNTX: NEXT SECTION!;
.COMPIL: NEXT SECTION!;
.COMPUT: NEXT SECTION!;
.end
LISP is a language for writing programs that do symbolic
computation. Information is coded or represented as S-expressions.
A LISP program can also be represented as an S-expression.
This gives LISP the special ability to easily manipulate
programs as well as other sorts of symbolic data.
In this chapter we describe notation for lists and
S-expressions, show how they are represented in a computer as list structures,
and describe the basic functions and predicates on the domain of S-expressions
in terms of the computer representation.
We then describe the
basic constructs of LISP and show how they are used to form LISP programs.
.ss(lists,Lists.)
We begin with some examples. The most common form of S-expression
is the list. Figure {fig f1} shows some examples of lists.
The list (i) has four elements, one of which is repeated.
The list (ii) has four elements one of which is itself a list.
The list (iii) has one element.
The list (iv) also has one element which itself is a list.
The list (v) has no elements; it is also written qNIL.
.GROUP
.BEGIN "f1"
.NOFILL
.TURNON "∂"
∂(30)(i)∂(40)$$(A B A E) $
∂(30)(ii)∂(40)$$(A B (C D) E)$
∂(30)(iii)∂(40)$$(A) $
∂(30)(iv)∂(40)$$((A B C D)) $
∂(30)(v)∂(40)$$() $
.TURNOFF
.END "f1"
!figf1 Examples of lists.!
.APART
Figure {fig f2} shows how symbolic information can be represented by lists.
Each example consists of a list and a "mathematical" representation of
the same information. Examples (i)-(iv) represent familiar mathematical
and logical expressions. The list (v)
is used to represent the network or graph shown according to a scheme
whereby there is a sublist for each vertex consisting of the vertex
itself followed by the vertices to which it is connected.
The elements of a list are surrounded by parentheses and
separated by spaces. A list may have any number of terms and any of
these terms may themselves be lists. In this case, the spaces
surrounding a sublist may be omitted, and extra spaces between
elements of a list are allowed. Thus__$$(A_B(C__D)____E)$__
and__$$(A_B_(C_D)_E)$__are slightly different ways of writing the same list.
.GROUP
.BEGIN "f2"
.SKIP 2
.TURNOFF "α" ;TURNON "∂";
.NOFILL
∂(10)(i) ∂(20)$$(PLUS X Y)$
∂(20)⊗⊗x + y⊗
∂(10)(ii) ∂(20)$$(PLUS (TIMES X Y) X 3)$
∂(20)⊗⊗xy + x + 3⊗.
∂(10)(iii) ∂(20)$$(EXIST X (ALL Y (IMPLIES (P X) (P Y))))$
∂(20)⊗⊗∃x: ∀y: [P(x)⊃P(y)]⊗.
∂(10)(iv) ∂(20)$$(INTEGRAL 0 ∞ (TIMES (EXP (TIMES I X Y)) (F X)) X)$
.TURN ON "↑↓[]&_∪";
∂(20)%8&%40%5↑∞%2e%5ixy%2f(x)dx%1.
.TURN OFF
∂(10)(v) ∂(20)$$((A B) (B A C D) (C B D E) (D B C E) (E C D F) (F E))$
.BEGIN "graph" SELECT D;
.PREFACE 0
.MILLPREFACE ← 0
.SKIP
∂(40)C
∂(38)≤'~`≥
∂(36)≤' ~ `≥
∂(32)B ≤' ~ `≥ E
∂(23)A αααααααα∂(33)'∂(33)≥∂(40)~∂(47)≤∂(47)`αααααααα F
∂(34)`≥ ~ ≤'
∂(36)`≥ ~ ≤'
∂(38)`≥~≤'
∂(40)D
.SKIP
.END "graph"
.TURNON TURNOFF
.END "f2"
!figf2 Information represented as lists.!
.APART
.ss(atoms,Atoms.)
The expressions $$A, B, X, Y, 3, PLUS$, and $$ALL$ occurring in the
lists in Figures {fig f1} and {fig f2} are
called atoms. In general, an atom is written as a
sequence of capital letters, digits, and special characters with
certain exclusions. The exclusions are <space>, <carriage return>,
and the other non-printing characters, and also the parentheses,
brackets, semi-colon, and comma. Numbers are expressed as signed
decimal or octal numbers, the exact convention depending on the
implementation. Floating point numbers are written with decimal
points and, when appropriate, an exponent notation depending on the
implementation. The reader should consult the programmer's manual
for the LISP implementation he intends to use.
Some further examples of atoms are shown in Figure {fig f2a}.
From such atoms we can form lists like
$$((345_3.14159_-47)_A307B_THE-LAST-TRUMP_-45.21)$.
.GROUP
.BEGIN "atoms"
.NOFILL
.CENTER
$$THE-LAST-TRUMP$
$$A307B $
$$345 $
$$-47 $
$$-45.21 $
$$3.14159 $
.END "atoms"
.skip
!figf2a Examples of atoms.!
.APART
.ss(liststruc,List structures.)
Atoms and lists are represented in the memory of the computer by
list structures. A list structure is a collection of memory units called
⊗cons-cells.
A cons-cell generally consists of one or possibly two consecutive computer
words. It is divided into two parts, the a-part and the d-part,
with each part being capable of containing an address in memory.
The list structure representing a list contains a cons-cell for each
element of the list. The a-part of the cell contains the address
of the list structure representing the element and the d-part contains
the address of the cell for the next element of the list.
These addresses are sometimes called pointers as they ``point'' to
the component list structures.
A diagram shows this more clearly than words. Figure_{fig f3} shows
the list structure corresponding to the list
__$$(PLUS_(TIMES_X_Y)_X_3)$__ (which might represent the expression
__⊗⊗xy_+_x_+_3⊗).
.GROUP
.BEGIN "f3"
.VERBATIM; SELECT C; PREFACE 0; MILLPREFACE ← 0;
⊂αααπααα⊃ ⊂αααπααα⊃ ⊂αααπααα⊃ ⊂αααπααα⊃
ααααα→~ ~ εαααα→~ ~ εαααα→~ ~ εαααα→~ ~ εααααααα⊃
%απα∀ααα$ %απα∀ααα$ %απα∀ααα$ %απα∀ααα$ ~
↓ ~ ~ ↓ ~
PLUS ~ ~ 3 ~
~ ⊂αααπααα⊃ ~ ⊂αααπααα⊃ ⊂αααπααα⊃ ~
%α→~ ~ εααβα→~ ~ εαααα→~ ~ ~ ~
%απα∀ααα$ ~ %απα∀ααα$ %απα∀απα$ ~
↓ ~ ~ ↓ ~ ~
TIMES %απαα$ Y %ααπα$
↓ ↓
X NIL
.END "f3"
!figf3 Representation of $$(PLUS (TIMES X Y) X 3)$ as a list structure.!
.APART
A program refers to a list by the address of the cell for its first
element. According to this convention, we see that the a-part of this
cell is the first element of the list and the d-part is a pointer to a
sublist formed by deleting the first element. Thus the first word of
the list structure of Figure_{fig f3} contains a pointer to the list
structure representing the atom $$PLUS$, while its d-part points to the
list $$((TIMES_X_Y)_X_3)$. The second word contains the list structure
representing $$(TIMES_X_Y)$ in its a-part and the list structure
representing $$(X_3)$ in its d-part. The last word points to the atom
$$3$ in its a-part and has a pointer to the atom qNIL in its d-part.
This is consistent with the convention that qNIL represents the null list.
Atoms are represented by the addresses of their property
lists which are list structures of a special kind depending on the
implementation.
(In some implementations, the first word of a
property list is in a special area of memory, in others the first word
is distinguished by sign, in still others it has a special a-part.
For basic LISP programming, it is enough to know that atoms are
distinguishable from other list structures by a predicate called
qqat.)
Each atom is represented uniquely, .e.g there is only one pointer
that prints as $$A$. In the diagram, we don't give the structure
of property lists but just label them with their ⊗⊗print names⊗.
A partial dump of the memory of a computer containing the list
structure of Figure_{fig f3}
might look as shown in Figure_{fig f4}.
Here %CX%* denotes the address of the property list of the atom
named $X and %C/3%* denotes that of the atom named $$3$.
Notice that the addresses of consecutive list elements need
not be consecutive.
Also the last word of a list cannot have the address of a next
word in its d-part since there isn't any next word, so it has the
address of a special atom called qNIL.
.GROUP
.BEGIN "f4"
.SELECT C
.TURNOFF "_"
.NOFILL
address a-part d-part address a-part d-part
_______ ______ ______ _______ ______ ______
86 TIMES 87 1000 PLUS 1001
87 X 88 1001 86 1002
88 Y NIL 1002 X 2653
2653 /3 NIL
.END "f4"
.skip
!figf4 A memory map for the list structure of Figure {fig f3}.!
.apart
.ss(sexp, S-expressions.)
When we examine the way list structures represent lists we
see a curious asymmetry. Namely, the a-part of a list word can
contain an atom or a list, but the d-part can contain only a list or
the special atom qNIL. This restriction is quite unnatural from the
computing point of view, and we shall allow arbitrary atoms to
inhabit the d-parts of words, but then we must generalize the way
list structures are expressed as character strings. To do this, we
introduce the notion of S-expression.
An S-expression is either an atom or a pair of S-expressions.
To write a non-atomic S-expression we write the pair of subexpression
separated by "_._" and surrounded by parentheses.
In BNF this rule is given by:
.SKIP
.BEGIN CENTER
<S-expression> ::= <atom> | (<S-expression> . <S-expression>).
.END
Figure {fig f5a} shows some examples of S-expressions.
.GROUP
.BEGIN "sexp"
.NOFILL
.CENTER
$$A $
$$(A . B) $
$$(A . (B . A)) $
$$(PLUS . (X . (Y . NIL))) $
$$(3 . 3.4) $
.END "sexp"
.skip
!figf5a Examples of S-expressions.!
.APART
In writing an S-expression,
the spaces around the "_._" may be omitted when this will not cause
confusion. The only possible confusion is of the dot separator with
a decimal point in numbers. Thus, in the above cases, we may write
$$(A.B)$, $$(A.(B.A))$, and $$(PLUS.(X.(Y.NIL)))$, but if we wrote $$(3.3.4)$
confusion would result.
In the memory of a computer, an S-expression is represented
by the address of a cons-cell whose a-part points to the first element of
the pair and whose d-part points to the second element of the pair.
Thus, the S-expressions $$(A.B)$, $$(A.(B.A))$, and $$(PLUS.(X.(Y.NIL)))$
are represented by the list structures of Figure_{fig f5}.
.GROUP
.BEGIN "f5"
.VERBATIM; SELECT C; PREFACE 0; MILLPREFACE ← 0;
⊂αααπααα⊃ ⊂αααπααα⊃ ⊂αααπααα⊃
αααα→~ ~ ~ αααα→~ ~ εαααα→~ ~ ~
%απα∀απα$ %απα∀ααα$ %απα∀απα$
↓ ↓ ~ ↓ ~
A B ~ B ~
~ ~
~ ~
%ααααααααπαααααααα$
↓
A
⊂αααπααα⊃ ⊂αααπααα⊃ ⊂αααπααα⊃
αααα→~ ~ εαααα→~ ~ εαααα→~ ~ ~
%απα∀ααα$ %απα∀ααα$ %απα∀απα$
↓ ↓ ↓ ↓
PLUS X Y NIL
.END "f5"
!figf5 Representation of S-expressions as list structures.!
.APART
Note that the list $$(PLUS_X_Y)$ and the S-expression
$$(PLUS_._(X_._(Y_._qNIL)))$ are represented in memory by the same list
structure. The simplest way to treat this is to regard S-expressions
as primary and lists as special kinds of S-expressions,
namely those that never have any atom but qNIL as the second part of
a pair. The list notation can then be considered as an
abbreviated way of writing these S-expressions,
Thus, the list notation $$(A_B_._._._Z)$ may be regarded
as an abbreviation of the S-expression notation
$$(A_._(B_._(C_._(..._(Z_._qNIL)_...))))$.
Note that the a-part of a list can be any S-expression,
but the d-part of a list must be a list and and the only atomic list is qNIL.
In giving input to LISP, either the list form or the
S-expression form may be used for lists. On output, LISP will print
a list structure as a list as far as it can, otherwise as an
S-expression. Thus, some list structures will be printed in a mixed
notation, e.g. $$((A_._B)_(C_._D)_(3))$. Some LISPs use an "extended"
list notation for printing S-expressions which minimizes the number of
parentheses and dots printed. In this notation
$$(A_._(B_._(C_._D)))$ would print as $$(A_B_C_._D)$.
(Programs for reading and printing S-expressions in the two notations
are given in Chapter_{section machin}.)
.skip
.item←0
.cb Exercises
#. If we represent sums and products as indicated above and
use $$(MINUS_X)$, $$(QUOTIENT_X_Y)$, and $$(POWER_X_Y)$ as representations
of ⊗-x, ⊗x/y, and ⊗⊗x%5y⊗ respectively, then
.NOFILL
a. What do the following lists represent?
⊗⊗⊗$$(QUOTIENT 2 (POWER (PLUS X (MINUS Y)) 3))$⊗
⊗⊗⊗$$(PLUS -2 (MINUS 2) (TIMES X (POWER Y 3.3)))$⊗
.FILL
b. How are the expressions ⊗⊗xyz+3(u+v)%5-3⊗
and ⊗⊗(xy-yx)/(xy+yx)⊗ to be represented?
#. In the above mentioned graph notation, what graph is
represented by the list
.SKIP
.BEGIN CENTER
$$((A D E F) (B D E F) (C D E F) (D A B C) (E A B C) (F A B C))$?
.END
#. Write the list $$(PLUS (TIMES X Y) X 3)$ as an S-expression.
This is sometimes referred to as "dot-notation".
#. Write the following S-expressions in list notation to
whatever extent is possible:
.NOFILL
a. $$(A . qNIL)$
b. $$(A . B)$
c. $$((A . qNIL) . B)$
d. $$((A . B) . ((C . D) . qNIL))$.
.FILL
#. How would you represent polynomials in one variable as lists?
Can you think of more that one way? How would you represent polynomials
in several variables? Can you tell if two lists represent the same
polynomial?
.if false then begin "omit"
#. Consider a data base of directory accounting information for
a computer center. For each directory the following information is
available: the account number, the project name, the names of programmers
using this directory, the protection status (a binary bit string),
the names of all files on this directory, and for each file the date it
was last written and name of the programmer who wrote it.
Represent this information using list structures. Show how the information
could be retrieved. For example could you produce a list of all files
written last by a given programmer using your representation of the data?
.end "omit"
(The next two mathematical exercises are unconnected with subsequent
material in this book.)
#. Prove that the number of "shapes" of S-expressions
with ⊗n atoms is ⊗⊗(2n - 2)!/(n!(n - 1)!)⊗. The two shapes
of S-expressions with three atoms are $$(A.(B.C))$ and $$((A.B).C)$.
These numbers are called Catalan numbers.
#. The above result can also be obtained by writing ⊗⊗S_=_A_+_S%8#%*S⊗
as an "equation" satisfied by the set of S-expressions with the
interpretation that an S-expression is either an atom or a pair of
S-expressions. The next step is to regard the equation as the
quadratic %2S%52%2_-_S_+_A = 0%1, solve it by the quadratic formula
choosing the minus sign for the square root. Then the radical is
regarded as the 1/2 power and expanded by the binomial theorem. Manipulating
the binomial coefficients yields the above formula as the coefficient
of %2A%5n%1 in the expansion. Why does this somewhat ill-motivated
and irregular procedure give the right answer?
.ss(basicfns, The basic functions and predicates on S-expressions.)
There are three basic functions on S-expressions:
⊗cons for constructing an S-expression from two given S-expressions,
and ⊗car and ⊗cdr for selecting the first and second components
of a non-atomic S-expression.
There are two predicates, ⊗atom for testing whether or not an S-expression
is atomic and ⊗eq for testing equality of atoms.
In this section we will describe the basic LISP programs
that compute these functions and predicates from list structure
representations of the arguments. All LISP programs for computing
functions and predicates on S-expressions are built
from these basic programs as will be explained in the sections following this.
This is analogous to numeric programs which are based on operations
computing the arithmetic functions of addition subtraction, multiplication,
and division, and the arithmetic predicates of equality and comparison.
First we introduce the notation to be used for writing LISP
terms. This notation will be extended in later sections to express
LISP programs as well. A LISP term is an expression intended
to denote an S-expression (the value of the term).
We will use two languages for writing LISP terms and programs -
⊗⊗internal language⊗ and ⊗⊗external language⊗.
Internal language represents LISP terms and programs as S-expressions.
Internal language programs are somewhat harder for a person
to read and write, but it is easier for a person to write a program
to manipulate ⊗object ⊗programs when the object programs are
in internal language (e.g. represented as S-expressions).
External language is a notation that is compact and easier
for people to read and write. However, external language programs
are not S-expressions, and therefore it is not easy to write LISP
programs to generate, interpret, compile or otherwise manipulate
programs written in external language. (An additional advantage of
the external notation is that it is very similar to the language used
to express facts about the abstract domain of S-expressions given
in Chapter_{section PROVIN}).
[Remark: most LISP implementations accept only internal
language programs.]
The simplest LISP terms are variables and constants.
In the external language the notation for S-expression constants
is that described in the preceeding sections. (S-expression constants
will always appear in the special font used in the previous sections.)
In the internal language there is a possible ambiguity as to whether
an S-expression is to represent itself, or the value of the LISP term
that it represents (if any). LISP takes the latter point of view.
An S-expression constant is represented by a list whose first element
is the atom $QUOTE and whose second element is the S-expression.
Thus the S-expression constant $$(A_B)$ is represented by the S-expression
$$(QUOTE_(A_B))$.
Variables are written in external notation as lower case italic identifiers.
Frequently just single letters such as ⊗x and ⊗u are used, but sometimes we
use names suggestive of the kind of object the variable represents.
The corresponding internal form will be the atom whose name is the same
identifier but in upper case (and appearing in the S-expression font).
Thus $X corresponds to ⊗x and $U to ⊗u.
We often use ⊗x, ⊗y, ⊗z to range over arbitrary S-expressions
and ⊗u, ⊗v, ⊗w to range over lists.
Additional terms (called application terms) can be formed denoting
the result of one of the basic LISP programs. These are expressed in external
language using ordinary mathematical notation for the application of functions
and predicates to a suitable number of arguments. Program names are used
for function symbols and variables or S-expression constants as arguments.
Argument lists will be surrounded by ``[]'' thus reserving parentheses for
S-expressions. The brackets will often be omitted for single arguments.
The internal notation for application terms is more uniform. Namely
such an application term is represented by a list, where the first element
is the atom corresponding to the program name and the remaining elements
of the list represent the arguments.
Table {table lsptrm}. gives some examples of LISP terms. Each
term is shown in external and internal notation along with the S-expression
value that it denotes. Note that no variables appear in these examples because
the value denoted by a LISP term containing a variable depends on
the value assigned to the variable.
.GROUP
.BEGIN "t1"
.TURNON "∂"
.NOFILL
.m←1 n1←8 n2←28 n3←68
∂(n1)External form ∂(n2)Internal form ∂(n3)Value denoted
∂(m)(i) ∂(n1)$$(A . B)$ ∂(n2)$$(QUOTE (A . B))$ ∂(n3)$$(A . B)$
∂(n1)$$(CAR X)$ ∂(n2)$$(QUOTE (CAR X))$ ∂(n3)$$(CAR X)$
∂(m)(iia) ∂(n1)qa $$(A . B)$ ∂(n2)$$(CAR (QUOTE (A . B)))$ ∂(n3)$$A$
∂(m)(iid) ∂(n1)qd $$(A . B)$ ∂(n2)$$(CDR (QUOTE (A . B)))$ ∂(n3)$$B$
∂(m)(iic) ∂(n1)⊗⊗cons[$$A,B$]⊗ ∂(n2)$$(CONS (QUOTE A) (QUOTE B))$ ∂(n3)$$(A . B)$
∂(m)(iiia) ∂(n1)qa $$((A . B) . A)$ ∂(n2)$$(CAR (QUOTE ((A . B) . A))$ ∂(n3)$$(A . B)$
∂(m)(iiid) ∂(n1)qd $$((A . B) . A)$ ∂(n2)$$(CDR (QUOTE ((A . B) . A))$ ∂(n3)$$A$
∂(m)(iiic) ∂(n1)⊗⊗cons[$$(A . B),A$]⊗ ∂(n2)$$(CONS (QUOTE (A . B)) (QUOTE A))$ ∂(n3)$$((A . B) . A)$
∂(m)(iva)∂(n1)qa $$(A B C D)$ ∂(n2)$$(CAR (QUOTE (A B C D)))$ ∂(n3)$$A$
∂(m)(ivd)∂(n1)qd $$(A B C D)$ ∂(n2)$$(CDR (QUOTE (A B C D)))$ ∂(n3)$$(B C D)$
∂(m)(ivc)∂(n1)⊗⊗cons[$$A,(B C D)$]⊗ ∂(n2)$$(CONS (QUOTE A) (QUOTE (B C D)))$ ∂(n3)$$(A B C D)$
∂(m)(v)∂(n1)qat $$A$ ∂(n2)$$(ATOM (QUOTE A))$ ∂(n3)$$T$
∂(n1)qat $$(A . B)$ ∂(n2)$$(ATOM (QUOTE (A . B))$ ∂(n3)$$NIL$
∂(m)(vi)∂(n1)$$A$ qeq $$A$ ∂(n2)$$(EQ (QUOTE A) (QUOTE A))$ ∂(n3)$$T$
∂(n1)$$A$ qeq $$B$ ∂(n2)$$(EQ (QUOTE A) (QUOTE B))$ ∂(n3)$$NIL$
∂(n1)$$(A . B)$ qeq $$(A . B)$ ∂(n2)$$(EQ (QUOTE (A . B)) (QUOTE (A . B)))$ ∂(n3)$$?$
.END "t1"
.TURNOFF
!tablelsptrm Examples of LISP terms in external and internal notation
and their values.!
.APART
We now describe the basic LISP programs and give their external and
internal names. The external names are generally abbreviations for the
internal names and will appear in bold face type.
We begin with the programs for the selector functions.
⊗car is represented externally by __qqa__ and internally by
$CAR. When applied to a non-atomic list structure the result is the a-part.
See Table {table lsptrm} (iia) and (iiia) for examples.
⊗cdr is represented externally by __qqd__ and internally by
$CDR. When applied to a non-atomic list structure the result is the d-part.
See Table {table lsptrm} (iid) and (iiid).
The action of the selector operations on atoms is not defined in basic LISP.
However, most implementations assign a some "meaning" to such terms, possibly
an error message.
Since lists are a particular kind of S-expression, the action of
the selector operations on non-empty lists is also determined by the above
definitions. In particular _qqa_ selects the first element of the list and
_qqd_ selects the rest of the list (e.g. the list formed by removing that
first element).
See Table {table lsptrm} (iva) and (ivd).
Recall that the a-part of a non-empty list can be any S-expression, while the
d-part is always a list. Thus the selectors behave symmetrically on
S-expressions but unsymmetrically on lists reflecting the symmetry properties
of the list structure representation of S-expressions and lists.
[Historical note:
the names "CAR" and "CDR" stood for "contents of the address part of register"
and "contents of the decrement part of register" in a 1957 precursor of LISP
projected for the IBM 704 computer. The names have persisted for
lack of a clearly preferable alternative.]
⊗cons is represented externally by qcons or (more often) by an
infixed ``_._'' and internally by $CONS. The program for ⊗cons must
have access to a supply of cons-cells called the free storage list.
Given pointers to two existing list structures, the program
removes a cons-cell from the free storage list and puts the first pointer
(address) into the a-part and the second into the d-part of this cell.
The result is the S-expression represented by the pointer to the new cons-cell.
See Table {table lsptrm} (iic) and (iiic).
We see that for lists, _⊗⊗cons⊗_ is a prefixing operation.
Namely, if the second argument is a list then the result of applying ⊗cons
is the list obtained by putting the first argument onto
the front of that list.
See Table {table lsptrm} (ivc).
[Note that giving the same pair of pointers to the ⊗cons program a
second time will result in the construction of
a list structure distinct from the first, although both represent the
same S-expression.]
The predicate ⊗atom is represented externally by qqat and
internally by $ATOM. The program for ⊗atom when given a pointer to
a list structure determines whether that list structure represents
and atom or not. The result is qT if the list structure
is atomic and qNIL otherwise.
See Table {table lsptrm} (v).
We see that the truthvalues qtrue and qfalse are represented in LISP
by the atoms qT and qNIL respectively.
The predicate ⊗eq is represented externally by the infix qeq
and internally by $EQ. As mentioned earlier, it is only required to
test for equality of atoms. The program for ⊗eq actually does a bit more.
Namely, given pointers to two list structures it compares these addresses.
If they are equal the result is qT, otherwise it is qNIL.
Since each atom is represented by a unique list structure,
the comparison is indeed a test
of equality if at least one of the arguments is atomic. More generally if
two list structures have the same address, they represent the same
S-expression. The converse is false because there is no guarantee
that the same S-expression is not represented by two different list structures.
(Two applications of ⊗cons to a pair of list structures in most
LISPs will result in two list structures representing the same S-expression,
but with different addresses.)
Equality of S-expressions is tested by a program based on ⊗eq which we will
describe in a later section. If this program were used instead of ⊗eq as
a basic function, LISP would be logically simpler, but many programs
would be slower.
This concludes the description of the basic LISP programs. To conclude
the section we give some further notational extensions, conventions and
abbreviations.
Besides the basic functions of LISP, there will be user-defined
functions. We haven't given the mechanism for function definition yet, but
suppose a function ⊗subst taking three arguments has been defined.
It may be used in terms like _⊗⊗subst[x,y,z]⊗_ having internal form
_$$(SUBST_X_Y_Z)$.
As in other programming languages and in mathematics generally,
application terms can have arbitrary terms as arguments, not just
variables and constants. Thus we have terms like
_⊗⊗[subst[x,y,qa z] . subst[x,y,qd z]]⊗_ involving
a user defined function ⊗subst. Its internal form is
_$$(CONS_(SUBST_X_Y_(CAR_Z))_(SUBST_X_Y_(CDR_Z)))$.
qn ⊗x _is an abbreviation for _⊗⊗x qeq qNIL⊗. It rates a special
notation because _qNIL_ plays the same role among lists that zero
plays among numbers, and list variables often have to be tested to
see if their value is qNIL.
Its internal form is $$(NULL X)$.
The notation _⊗⊗list[x1,_x2,_._._._,xn]⊗_ is used to denote the
composition of %2cons%1's that forms a list from its elements. Thus
_⊗⊗list[x,_y,_z]⊗_ denotes _⊗⊗cons[x,_cons[y,_cons[z,_qNIL]]]⊗_
and forms a list of three elements out of the quantities ⊗x, ⊗y, and
⊗z. We often write _⊗⊗<x,_y,_._._.,_z>⊗_ instead of _⊗⊗list[x,_y,_._._._,_z]⊗_
when this will not cause confusion. The experienced
implementer of programming languages will expect that since ⊗list has a
variable number of arguments, its implementation will pose problems. That
is indeed true. The internal form of _⊗⊗<x,_y,_._._.,_z>⊗_ is
_$$(LIST_X_Y_._._._Z)$.
Compositions of qqa and qqd are written by concatenating the
letters qqa and qqd. Thus, it is easily seen that qad ⊗u denotes
the second element of the list ⊗u, and qadd ⊗u denotes the third
element of that list. The internal names of these functions are
$CADR and $CADDR respectively.
In external language, we often omit brackets for functions
of one argument. Thus _⊗⊗alt_x⊗_ stands for _⊗⊗alt[x]⊗,_ and _⊗⊗alt_alt_x⊗_
stands for _⊗⊗alt[alt[x]]⊗_. This convention was also used in the
descriptions of qqa, qqd, qqat, and qqn.
.skip 2
.GROUP
.cb Exercise
.item←0
#. What is the value of ⊗⊗< $A . qa $$(B . C)$, $D . qd $$(B . C)$>⊗?
#. What combinations of qqa and qqd select $$(X Y)$ and $$(CONS X Y)$
respectively from
⊗⊗⊗$$((LAMBDA (X Y) (CONS X Y)) (QUOTE A) (QUOTE B))$⊗
.APART
.ss(cond,Conditional terms.)
When the value of a function depends on whether a
certain predicate is true of the arguments, conditional terms
are used to describe the function. In external language a simple
conditional term has the form
!eqnaa1 ⊗⊗⊗qif p qthen a qelse b ⊗
where ⊗p is a propositional term and ⊗a and ⊗b can be any terms.
By propositional term we mean a term whose value represents a truthvalue
(qtrue or qfalse). A (program computing a) predicate applied to a list of
arguments is a propositional term. We will explain how to form such terms
in general in the next section.
The conditional term {eqn aa1}
is evaluated as follows: first _⊗p _is evaluated and determined to be
true or false. If ⊗p is true, then ⊗a is evaluated and its value
is the value of the expression. If ⊗p is false, then ⊗b is
evaluated and its value is the value of the expression. Note that if
⊗p is true, ⊗b is never evaluated, and if ⊗p is false, then ⊗a is
never evaluated. The importance of this will be explained later.
A familiar function that can be written conveniently using conditional
expressions is the absolute value of a real number. We have
!eqnaa2 ⊗⊗⊗|x| = qif x<0 qthen -x qelse x⊗.
.GROUP;
[Remark: The common mathematical notation for such definitions is
.BEGIN
.NOFILL
.PREFACE 0
.MILLPREFACE ← 0
.TURNON "∂"
.m←30 n←36
∂(n)%8/%* _⊗x if ⊗⊗x ≥ 0⊗
∂(m) ⊗⊗|x|⊗ = ∂(n)%8[%*
∂(n)%8\%* ⊗-x otherwise,
.TURNOFF
.END
but the right hand side is not allowed to be part of another expression.]
.APART
More generally a conditional term has the form
!eqnaa3 ⊗⊗⊗qif p qthen a qelse qif q qthen b . . . qelse qif s qthen d qelse e⊗.
There can be any number of clauses. The value is determined by
evaluating the propositional terms ⊗p, ⊗q, etc. until a true term is
found, the value is then that of the term following the next qthen.
If none of the propositional terms is true, then the value is that of
the term following the last qelse.
Figure {fig f6} shows an example of a (numeric) function defined
using a conditional expression.
.GROUP;
.BEGIN SELECT D;
.NOFILL
.PREFACE 0
.MILLPREFACE ← 0
.TURNOFF "α"
.SKIP 4
(0,1)
≤'`≥
≤' `≥
↑ ≤' `≥
~ ≤' `≥
tri[x] ~ αααααααααααααααα' `αααααααααααααααα
~ (-1,0) (1,0)
ααα→
x
.SKIP 2
⊗⊗⊗tri[x] = qif x<-1 qthen 0 qelse qif x<0 qthen 1+x qelse qif x<1 qthen 1-x qelse 0⊗.
.TURNON
.END
!figf6 The triangle function.!
.APART
The conditional term in internal language has the form
!eqnaa4 ⊗⊗⊗$$(COND %2(p1 e1) (p2 e2) ... (pn en)%*)$⊗
with any number of ⊗p-e pairs. Its value is determined by evaluating the
⊗⊗p⊗'s successively until one is found with a value corresponding to qtrue.
The value of the
corresponding ⊗e is then taken as the value of the conditional term.
If none of the ⊗⊗p⊗'s is true, then the value of the conditional
term is undefined. (In some implementations the conditional term
is given a default value such as qNIL if none of the ⊗⊗p⊗'s are true.)__
[Remark:
In the internal form, all the ⊗⊗e⊗'s are treated the same
which makes programs for interpreting or compiling conditional
expressions easier to write. This is another way in which expressions
in internal language are more
regular than in external language.
]
Conditional expressions may be compounded with functions to
get terms like
!eqnaa5 ⊗⊗⊗qif qn u qthen v qelse qa u . append[qd u, v] ⊗
involving a yet to be defined function ⊗append. The internal
form of this is
!eqnaa6 ⊗⊗⊗$$(COND ((NULL U) V) (T (CONS (CAR U) (APPEND (CDR U) V))))$.⊗
One would normally have expected to write
$$(QUOTE T)$, but there is a special convention that
qT may be written without $QUOTE. This convention applies to qNIL also.
This means that
these symbols cannot be used as variables. As mentioned
in section qsect {subsection basicfns}, qT represents
the propositional constant qtrue, i.e. it is always true
so that it is impossible to "fall off the end" of a conditional
expression with qT as its last ⊗p. It is the translation
into internal form of the final qelse of a conditional
expression in external form.
.ss(andor,Propositional terms.)
As mentioned in the previous section,
propositional terms are a terms whose value represents a truth value.
The simplest propositional terms are the constants qT and qNIL.
If qp is a predicate of n-arguments then ⊗⊗qp[x1,_._._._,xn]⊗ is a
propositional term. Additional propositional terms can be formed by combining
terms already formed using the logical operations of
conjunction(qand), disjunction(qor) and negation(qnot).
Both qand and qor are associative, so we can write expressions
like _⊗⊗p1_qand_p2_qand_p3⊗_ without worrying about the grouping.
The value of a propositional term can be determined using the truth
table given in Table_{table propop}.
.GROUP
.BEGIN turnon "∂"
.NOFILL n1←12 n2←36 n3←56
∂(n1) qT qand qT = qT ∂(n2) qT qor qT = qT
∂(n1) qT qand qNIL = qNIL ∂(n2) qT qor qNIL = qT ∂(n3)qnot qT = qNIL
∂(n1)qNIL qand qT = qNIL ∂(n2)qNIL qor qT = qT ∂(n3)qnot qNIL = qT
∂(n1)qNIL qand qNIL = qNIL ∂(n2)qNIL qor qNIL = qNIL
.END
!tablepropop Truth table for propositional terms.!
.APART
The evaluation of propositional terms is defined using conditional
terms as follows:
.BEGIN NOFILL
!fcnand&d ⊗⊗⊗p qand q = qif p qthen q qelse qNIL⊗
!fcnor&r ⊗⊗⊗ p qor q = qif p qthen p qelse q⊗
!fcnnot&t ⊗⊗⊗ qnot p = qif p qthen qNIL qelse qT⊗
.END
The internal forms of these definitions are
.BEGIN NOFILL
⊗⊗⊗$$(AND P Q) = (COND (P Q) (T NIL))$⊗
⊗⊗⊗$$ (OR P Q) = (COND (P P) (T Q)) $⊗
⊗⊗⊗$$ (NOT P) = (COND (P NIL) (T T))$⊗
.END
Note that if ⊗p is false then _⊗⊗p_qand_q_=_qNIL⊗_ independent of the value of
⊗q, and likewise if ⊗p is true, then _⊗⊗p_qor_q_=_qT⊗_ independent of
⊗q. If ⊗p has been evaluated and found to be false, then ⊗q does
not have to be evaluated at all to find the value of ⊗⊗p_qand_q⊗, and, in
fact, LISP does not evaluate ⊗q in this case. Similarly, ⊗q is not
evaluated in evaluating ⊗⊗p_qor_q⊗ if ⊗p is true. This procedure is in
accordance with the above conditional expression descriptions of
these operators. The importance of this convention, which contrasts
with that of ALGOL 60, will be apparent later when we discuss
recursive definitions of functions and predicates.
Propositional expressions can be combined with functions and conditional
expressions to get terms like
!eqnac4 ⊗⊗⊗qif [qn u qor qn qd u] qthen u qelse qa u . alt qdd u⊗
whose internal form is
!eqnac5 ⊗⊗⊗$$ (COND ((OR (NULL U) (NULL (CDR U))) U) (T (CONS (CAR U) (ALT (CDDR U)))))$⊗.
We conclude this section with two remarks. First, the only
S-expressions that we have said represent truthvalues are qT and qNIL.
However, most LISP implementations regard any non-qNIL S-expression as
representing qtrue. These LISPs do not distinguish between between
propositional terms and more general terms. Thus any term can appear in
the ⊗p part of a conditional term. Second,
most LISP implementations allow qand and qor to have arbitrary numbers
of arguments. Since these operations are associative, this can be viewed
as simply omitting parentheses as it won't matter how the arguments are grouped.
.ss(recdefn,Recursive function definitions.)
In such languages as FORTRAN and ALGOL, computer programs
are expressed in the main as sequences of assignment statements and
conditional %3go to%1's. In LISP, programs are mainly expressed in the
form of recursively defined functions. We begin with an example.
We want a function ⊗alt such that ⊗⊗alt_u⊗ gives a list whose
elements are
alternate elements of the list ⊗u beginning with the first. For example
we want
.begin nofill group
⊗⊗⊗ alt $$(A B C D E)$ = $$(A C E)$⊗,
⊗⊗⊗ alt_$$((A B) (C D))$ = $$((A B))$⊗,
⊗⊗⊗ alt_$$(A)$ = $$(A)$, ⊗
⊗⊗⊗ alt qNIL = qNIL. ⊗
.end
and in LISP we can define ⊗alt by the recursion equation
!fcnalt& ⊗⊗⊗alt_u ← qif qn u qor qn qd u qthen u qelse qa u . alt_qdd u⊗.
In case you need a review of our precedence conventions, fully bracketed
it looks like
⊗⊗⊗alt[u] ← [qif [qn [u] qor qn [qd [u]]] qthen u qelse [qa [u] . alt[qdd [u]]]]⊗.
The terms appearing in the recursion equation are formed by the methods
previously discussed. Notice that the function ⊗alt occurs in
the right hand side of its own defining equation and
that we use "←" instead of "=" . The recursion equation
tells us that ⊗alt is a function of one variable ⊗u, and that the value of
⊗⊗alt u⊗ for some particular list is computed by evaluating the right hand side
of the definition, substituting that list for ⊗u whenever ⊗u is
encountered and re-evaluating the right hand side with a new
⊗u whenever a term ⊗⊗alt e⊗ is encountered.
This process is best illustrated by evaluating some expressions.
Consider evaluating ⊗⊗alt_qNIL⊗.
We do it by evaluating the expression to the right of the _"←"_ in {eqn alt}
remembering that the variable ⊗u has the value qNIL. A conditional
expression is evaluated by first evaluating the first propositional
term - in this case ⊗⊗qn u qor qn qd u⊗.
This expression is a disjunction
so we first evaluate the first disjunct, namely qn ⊗u.
(Recall the convention given in section qsect {subsection andor}).
Since _⊗⊗u = qNIL⊗, _⊗⊗qn u⊗_ is true, the disjunction is true, and the value
of the conditional expression is the value of the term after the
first true propositional term. This term is ⊗u, and its value is
qNIL, so the value of _⊗⊗alt[qNIL]⊗_ is qNIL. Obeying
the rules about the order of evaluation of terms in conditional and
propositional expressions is important in this case since if we didn't obey
these rules, we might find ourselves trying to evaluate _⊗⊗qn qd u⊗_ or
_⊗⊗alt[qdd u]⊗, and since ⊗u is qNIL, neither of these has a value.
(An attempt to evaluate them would result in an error return in
most LISPs.)
As a second example, consider _⊗⊗alt_$$(A_B)$⊗. Since neither
qn ⊗u nor qn qd ⊗u is true in this case, the disjunction _⊗⊗qn u qor qn qd u⊗_
is false and the value of the expression is the value of
_⊗⊗qa u_._alt_qdd u⊗. qa ⊗u has the value $A, and qdd ⊗u has the value
qNIL, so we must now evaluate ⊗⊗alt_qNIL⊗, and we already know that this
is qNIL. Therefore, the value of
_⊗⊗alt_$$(A_B)$⊗_ is that of _$$A_._qNIL$_ which is _$$(A)$.
This evaluation is described by the following sequence of equations:
.if lines < 5 then next page;
.begin nofill turnon "∂"
∂(10)⊗⊗alt_$$(A B)$⊗ ∂(18)⊗⊗= qif [qn $$(A B)$ qor qn qd $$(A B)$] qthen $$(A B)$
qelse qa $$(A B)$ . alt[qdd $$(A B)$]⊗
∂(18)⊗⊗= qif [qfalse qor qn qd $$(A B)$] qthen $$(A B)$ qelse qa $$(A B)$ . alt[qdd $$(A B)$] ⊗
∂(18)⊗⊗= qif qfalse qthen $$(A B)$ qelse qa $$(A B)$ . alt[qdd $$(A B)$]⊗
∂(18)⊗⊗= qa $$(A B)$ . alt[qdd $$(A B)$]⊗
∂(18)⊗⊗= $A . alt[qNIL]⊗
∂(18)⊗⊗= $A . qif [qn qNIL qor qn qd qNIL] qthen qNIL
qelse qa qNIL . alt[qdd qNIL]⊗
∂(18)⊗⊗= $A . qif [qtrue qor qn qd qNIL] qthen qNIL
qelse qa qNIL . alt[qdd qNIL]⊗
∂(18)⊗⊗= $A . qif qtrue qthen qNIL
qelse qa qNIL . alt[qdd qNIL]⊗
∂(18)⊗⊗= $A . qNIL⊗
∂(18)⊗⊗= $$(A)$⊗.
.end
This is still very long-winded, and now that the reader
understands the order of evaluation of conditional and propositional
expressions, we can proceed more briefly to evaluate
.begin nofill group turnon "∂"
∂(15)⊗⊗alt[$$(A B C D E)$]⊗∂(30)⊗⊗= $A . alt[$$(C D E)$]⊗
∂(30)⊗⊗= $A . [$C . alt[$$(E)$]]⊗
∂(30)⊗⊗= $A . [$$(C E)$]⊗
∂(30)⊗⊗= $$(A C E)$⊗.
.end
Here are three more examples of recursive functions and their
application. We define ⊗last by
!fcnlast& ⊗⊗⊗last u ← qif qn qd u qthen qa u qelse last qd u⊗,
and we compute
.begin nofill group turnon "∂"
∂(19)⊗⊗last $$(A B C)$⊗∂(30)⊗⊗= qif qn qd $$(A B C)$ qthen qa $$(A B C)$
qelse last qd $$(A B C)$⊗
∂(30)⊗⊗= last_$$(B C)$⊗
∂(30)⊗⊗= last_$$(C)$⊗
∂(30)⊗⊗= $$C$⊗.
.end
Clearly _⊗last _computes the last element of a list. ⊗⊗last_qNIL⊗ is
undefined in the LISP language; the result of trying to compute it
may be an error message or may be some random result depending on the
implementation. (A heavy duty version of ⊗last would explicitly
call a function called ⊗error with a string expressing the complaint
that the program had tried to compute ⊗last qNIL.)__
The function _⊗subst _is defined by
!fcnsubst& ⊗⊗⊗subst[x, y, z] ← qif qat z qthen [qif z qeq y qthen x qelse z]
qelse subst[x,y,qa z] . subst[x,y,qd z]⊗.
We have
.begin nofill group turnon "∂"
∂(4)⊗⊗subst[$$(A.B), X, ((X.A).X)$] ⊗∂(30)⊗⊗= subst[$$(A.B), X, (X.A)$] . subst[$$(A.B), X, X$]⊗
∂(30)⊗⊗= [subst[$$(A.B), X, X$] . subst[$$(A.B), X, A$]] . $$(A.B)$⊗
∂(30)⊗⊗= [[$$(A.B)$].$$A$].$$(A.B)$]⊗
∂(30)⊗⊗= $$(((A.B).A).(A.B))$⊗.
.end
⊗subst computes the result of substituting the S-expression ⊗x for
the atom ⊗y in the S-expression ⊗z. This operation is important
in all kinds of symbolic computation.
The function ⊗⊗append[u,v]⊗ which gives the concatenation of the lists
⊗u and ⊗v is also important. It is also denoted by the
infixed expression _⊗⊗u * v⊗. For example we have
.begin nofill group
⊗⊗⊗$$ (A B C)$ * $$(D E F)$ = $$(A B C D E F)$,⊗
⊗⊗⊗qNIL * $$(A B)$ =$$(A B)$ = $$(A B)$ * qNIL,⊗
.end
and the formal definition
!fcnappend& ⊗⊗⊗u * v ← qif qn u qthen v qelse qa u . [qd u] * v⊗.
The ⊗append function is machine coded in most Lisp systems
in a way that allows an arbitrary number of arguments, e.g.
$$(APPEND (QUOTE (A B)) (QUOTE (C D)) (QUOTE (E F)))$ is $$(A_B_C_D_E_F)$.
It is convenient to use an infix for ⊗append because it is associative,
i.e. _⊗⊗u * [v * w] = [u * v] * w⊗ so we can just write _⊗⊗u * v * w⊗.
We often use infix notation for recursively defined functions
when it is mathematically conventional or convenient.
The propositional operations can also be used in making recursive
definitions since we take advantage of the order of evaluation of
constituents. Thus, we define a predicate _⊗equal _by
!fcnequal& ⊗⊗⊗equal[x,y] ← x qeq y qor [qnot qat x qand qnot qat y qand
equal[qa x,qa y] qand equal[qd x, qd y]]⊗.
⊗⊗equal[x,y]⊗ is true if and only if ⊗x and ⊗y are the same
S-expression, and the use of this predicate makes up for the fact
that the basic predicate qeq is guaranteed to test equality only
when one of the operands is known to be an atom. We shall also use
the infixes _%3=%1_ and _%3≠%1.
Membership of an S-expression ⊗x in a list ⊗u is tested by
!fcnmember& ⊗⊗⊗member[x, u] ← qnot qn u qand [[x = qa u] qor member[x, qd u]]⊗.
This relation is also denoted by ⊗⊗x_ε_u⊗. Here are some computations:
.begin nofill group turnon "∂"
∂(13)⊗⊗member[$B, $$(A B)$]⊗∂(30)⊗⊗= qnot qn $$(A B)$ qand [[$B = qa $$(A B)$]
qor member[$B, qd $$(A B)$]]⊗,
∂(30)⊗⊗= member[$B, $$(B)$]⊗
∂(30)⊗⊗= qtrue⊗.
.end
Sometimes a function is defined with the help of auxiliary
functions. Thus, the reverse of a list ⊗u , (e.g.
_⊗⊗reverse[$$(A_B_C_D)$]_=_$$(D_C_B_A)$⊗), is given by the pair of equations
.begin nofill group
⊗⊗⊗reverse[u] ← rev[u, qNIL]⊗
!fcnreverse&
⊗⊗⊗rev[u, v] ← qif qn u qthen v qelse rev[qd u, [qa u].v]⊗.
.end
A computation is:
.begin nofill group turnon "∂"
∂(16)⊗⊗reverse[$$(A B C)$]⊗∂(30)⊗⊗= rev[$$(A B C)$, qNIL]⊗
∂(30)⊗⊗= rev[$$(B C), (A)$]⊗
∂(30)⊗⊗= rev[$$(C), (B A)$]⊗
∂(30)⊗⊗= rev[qNIL, $$(C B A)$]⊗
∂(30)⊗⊗= $$(C B A)$⊗.
.end
A more elaborate example of recursive definition is given by
.begin nofill group
⊗⊗⊗flatten[x] ← flat[x, qNIL] ⊗
!fcnflatten&
⊗⊗⊗flat[x, u] ← qif qat x qthen x.u qelse flat[qa x, flat[qd x, u]]⊗.
.end
We have
.begin nofill group turnon "∂"
∂(12)⊗⊗flatten[$$((A.B).C)$]⊗∂(30)⊗⊗= flat[$$((A.B).C)$, qNIL]⊗
∂(30)⊗⊗= flat[$$(A.B)$, flat[$C, qNIL]]⊗
∂(30)⊗⊗= flat[$$(A.B), (C)$]⊗
∂(30)⊗⊗= flat[$A, flat[$$B, (C)$]]⊗
∂(30)⊗⊗= flat[$$A, (B C)$]⊗
∂(30)⊗⊗= $$(A B C)$⊗.
.end
The reader will see that the value of ⊗⊗flatten[x]⊗ is a list of the
atoms of the S-expression ⊗x from left to right. Thus
⊗⊗flatten[$$((A_B)_A)$]_=_$$(A_B_NIL_A_NIL)$⊗.
Many functions can be conveniently written in more than one
way. For example, the function ⊗reverse mentioned above can be
defined without an auxiliary function as follows:
!fcnreversea& ⊗⊗⊗reverse1 u ← qif qn u qthen qNIL qelse reverse1 qd u * <qa u>⊗,
but the earlier definition involves less computation,
because * takes time proportional to the length of its first argument.
Similarly the function computed by ⊗flatten can also be computed by the
simpler but less efficient program ⊗fringe
!fcnfringe& ⊗⊗⊗fringe x ← qif qat x qthen <x> qelse fringe qa x * fringe qd x⊗,
The use of conditional expressions for recursive function
definition is not limited to functions of S-expressions. For
example, the factorial function and the Euclidean algorithm for the
greatest common divisor on the non-negative integers may be written
as follows:
!fcnfact& ⊗⊗⊗n! ← qif n=$0 qthen $1 qelse nq*[n-$$1$]!⊗
and
!fcngcd& ⊗⊗⊗gcd[m, n] ← qif m>n qthen gcd[n, m] qelse qif m=$0 qthen n qelse gcd[n mod m, m]⊗
where ⊗⊗n mod m⊗ denotes the remainder when ⊗n is divided by ⊗m and
may itself be expressed recursively by
!fcnmod&d ⊗⊗⊗n mod m ← qif n<m qthen n qelse [n-m] mod m⊗.
(Note that these definitions must be modified if negative integers
are to be included in the domain.)
The internal form of function definitions depends on the implementation.
MACLISP uses the form
.once center
($DEFUN <function name> <list of variables> <right hand side>).
Stanford LISP and UCI LISP for the PDP-10 computer use the same form with $DE
in place of $DEFUN. Thus in MACLISP the definition of ⊗subst is
.begin nofill select 6 group indent 6,6
(DEFUN SUBST (X Y Z)
(COND ((ATOM Z) (COND ((EQ Z Y) X) (T Z)))
(T (CONS (SUBST X Y (CAR Z)) (SUBST X Y (CDR Z)))))),
.end
and the definition of ⊗alt is
.begin nofill group select 6 indent 8,8
(DEFUN ALT (U)
(COND ((OR (NULL U) (NULL (CDR U))) U)
(T (CONS (CAR U) (ALT (CDDR U)))))).
.end
Yet another notation for function definition called the $DEFPROP notation
will be explained after λ-expressions have been introduced.
.SKIP
.item←0
.cb Exercises
#. Consider the function ⊗drop defined by
⊗⊗⊗drop[u] ← qif qn u qthen qNIL qelse <qa u> . drop[qd u]⊗.
Compute (by hand) ⊗⊗drop[$$(A B C)$]⊗. What does ⊗drop do to lists in
general? Write ⊗drop in internal notation using $DEFUN.
#. What does the function
⊗⊗⊗r2[u] ← qif qn u qthen qNIL qelse reverse[qa u] . r2[qd u]⊗
do to lists of lists? How about
⊗⊗⊗r3[x] ← qif qat x qthen x qelse reverse[r4[x]] ⊗
⊗⊗⊗r4[u] ← qif qn u qthen qNIL qelse r3[qa u] . r4[qd u]? ⊗
#. Compare
⊗⊗⊗r3'[x] ← qif qat x qthen x qelse <r3'[qd x]> * <r3'[qa x]>⊗
with the function ⊗r3 of the preceding example.
#. Consider ⊗r5 defined by
⊗⊗⊗r5[u] ← qif qn u qor qn qd u qthen u
qelse [qa r5[qd u]] . r5[qa u . r5[qd r5[qd u]]]⊗.
Compute ⊗⊗r5[$$(A B C D)$]⊗. What does ⊗r5 do? Needless to
say, this is not a good way of computing this function even though it
involves no auxiliary functions. [This ingenious program was discovered
by S. Ness]
.if false then begin "answers"
⊗r2 returns the list with each of its elements reversed.
⊗r3, ⊗r4 maps a general list structure into one with 1st 3rd ... oddth level
lists reversed, even level lists in original order.
⊗r3' returns the mirror image of an S-expression
⊗r5 reverses a list.
.end "answers"
.ss(numbers,Numerical computation.)
.<<eqn labels ag>>
Numerical calculation and symbolic calculation must often
be combined, so LISP provides for numerical computation also.
(Numbers could be represented as lists of digits, but then it
would be difficult to take proper advantage of machine instructions
that work with numbers directly).
Since we need to include numbers as parts
of symbolic expressions, LISP has both integer and floating point
numbers which are regarded as atoms that
may be included as atoms in writing S-expressions.
Thus we have the lists:
.begin nofill select 6 group turnon "∂"
.n←30
∂(n)(1 3 5)
∂(n)(3.5 6.1 -7.2E9)
∂(n)(PLUS X 1.3).
.end
The first
is a list of integers, the second a list of floating point numbers,
and the third a symbolic list containing both numerical and
non-numerical atoms. Integers are written without decimal points
which are used to signal floating point numbers. As in FORTRAN,
the letter E is used to signal the exponent of a floating point
number which is a signed integer. The sizes of numbers admitted
depends on the implementation. When a dotted pair, say $$(1 . 2)$
is wanted, the spaces around the dot distinguish it from the
list $$(1.2)$ whose sole element is the floating point number 1.2.
In external language we will use ordinary mathematical
notation for numerical functions. As an example of a function
combining numeric and symbolic calculation we have the function
giving the length of a list defined by
!fcnlength&h ⊗⊗⊗length u ← qif qn u qthen 0 qelse 1 + length qd u⊗.
The internal notation for numerical functions is shown in
the following examples:
.begin nofill group turnon "∂"
.n←30
∂(n)$$(PLUS X Y ... Z)$ for ⊗⊗x+y+...+z⊗,
∂(n)$$(TIMES X ... Z)$ for ⊗⊗xy...z⊗,
∂(n)$$(MINUS X)$ for ⊗⊗-x⊗,
∂(n)$$(DIFFERENCE X Y)$ for ⊗⊗x-y⊗,
∂(n)$$(QUOTIENT X Y)$ for ⊗⊗x/y⊗,
∂(n)$$(POWER X Y)$ for ⊗⊗x%5y⊗.
.end
Besides functions of numbers we need predicates on numbers
and the usual =, <, >, ≤, and ≥ are used with the internal
names $EQUAL, $LESSP, $GREATERP, $LESSEQP, and $GREATEREQP, respectively.
Not all are implemented in all LISP systems, but of course the
remaining ones can be defined. An additional predicate, ⊗numberp,
is used to distinguish numbers from other atoms.
Since numbers that form part of list structures must be
represented by pointers anyway, there is room for a flag distinguishing
floating point numbers and integers. Therefore, the arithmetic
operations are programmed to treat types dynamically, i.e. a variable
may take an integer value at one step of computation and a real value
at another. The subroutines realizing the arithmetic functions make
the appropriate tests and create results of appropriate types.
It is worth remarking that including type flags in numbers
would benefit many programming languages besides LISP and would
not cost much in either storage or hardware.
Dynamic typing of variables is slow compared to direct use of
the machine's arithmetic instructions, so that LISP can be efficiently
used interpretively only when
the numerical calculations are small or at least small compared
to the symbolic calculations in a problem.
The MACLISP compiler NCOMPLR is able to generate efficient
arithmetic code. In particular, variables can be declared to be of a fixed
numerical type and the correct machine instructions are then generated
so that runtime testing is not necessary. Also, it uses separate stacks
to store numerical results so that unecessary conversion from the
LISP representation of a number to the machine representation can be
avoided. This saves both time and space as each conversion from a
machine number to a LISP number requires a ⊗cons operation.
LISP can also deal with integers too large to be represented
as a single machine word. Such numbers are called "bignums" and
are repsented in LISP by a pointer to a list structure which contains the
sign, a flag saying that this a "bignum", and a list of the numbers
corresponding to a base B representation of the number for some
suitable B (depending on the machine and implementation).
As another example of a combined numeric and symbolic
computation, we give an evaluator for expressions with sums and
products.
The expressions are built up from atoms
denoting variables and integer constants according to the syntax
.begin nofill
<expression> ::= <variable> | <integer> | ($PLUS <explist>) | ($TIMES <explist>)
!eqnexpr
<explist> ::= <expression> | <expression><explist>
.end
Thus a list of expressions beginning with the atom $PLUS represents the sum
of these expressions and a list of expressions beginning with the atom
$TIMES represents the product of these expressions.
In order to evaluate an expression we need a way of giving values to the
variables occuring in the expression. We will use an ⊗association ⊗list for
this purpose. An association list (a-list) is a list of pairs, in our
case the first
element of each pair is a variable and the second element is the value associated
with it. For example $$((X . 5) (Y . 9.3) (Z . 2.1))$ is an a-list.
To look up the value of a variable in an a-list we use the function ⊗assoc,
which returns the first pair in the list such that the variable matches
the variable argument. It returns qNIL if no value is found. Thus
⊗⊗⊗assoc[$$Y$, $$((X . 5) (Y . 9.3) (Z . 2.1))$] = $$(Y . 9.3)$⊗
and the definition of ⊗assoc is given by
!fcnassoc& ⊗⊗⊗assoc[x,a] ← qif qn a qthen qNIL qelse qif qaa a qeq x qthen qa a qelse assoc[x,qd a].⊗
Association lists are generally useful for associating "values" with "symbols" and
they will appear in many later examples. We note here two features
which are due to the way ⊗assoc is defined. Since ⊗assoc returns the
pair rather than the value when the desired symbol is found or qNIL
if no value is found, the case of no value found can be detected.
If just the value were returned there would be no distinction between no
value and a value of qNIL. The calling program must check to see if a value
was returned (⊗⊗qnot qn assoc[x,a]⊗) and then extract that value (⊗⊗qd assoc[x,a]⊗).
Also, ⊗assoc returns the first pair it finds, thus a symbol can be associated
with several values in the a-list, but always the first occurence determines
the result that is returned. Thus
⊗⊗⊗assoc[$$X$,$$((U . 1.41) (X . 5) (Y . 9.3) (X . 1.2) (Z . 2.1))$] = $$(X . 5)$⊗.
⊗assoc is built into most LISP systems.
The interpreter, ⊗numval, can now be defined.
.begin nofill group turnon "∂"
.n←24
∂(12)⊗⊗numval[e,a]⊗ ∂(n)⊗⊗← qif numberp e qthen e⊗
∂(n)⊗⊗ qelse qif qat e qthen qd assoc[e,a]⊗
!fcnnumval& ∂(n)⊗⊗ qelse qif qa e qeq $PLUS qthen evplus[qd e,a]⊗
∂(n)⊗⊗ qelse qif qa e qeq $TIMES qthen evtimes[qd e,a]⊗
where
!fcnevplus& ⊗⊗⊗ evplus[u,a] ← qif qn u qthen 0 qelse numval[qa u,a] + evplus[qd u,a], ⊗
!fcnevtimes& ⊗⊗⊗evtimes[u,a] ← qif qn u qthen 1 qelse numval[qa u,a] q* evtimes[qd u,a], ⊗
.end
.ss(bool,Bitwise Boolean Operations)
Besides the usual arithmetic operations on numbers, LISP
allows bitwise boolean operations on words in memory. Letting
⊗m, and ⊗n be strings of $$1$s and $$0$s
of some fixed length depending on the machine word size,
then ⊗⊗m %3bool-op%* n⊗
denotes the word whose binary repsentation is given by performing the
boolean operation on each pair of corresponding bits.
Thus we have
.begin nofill center
$$4 %3bool-and%* 6 = 4$
$$ 4 %3bool-or%* 6 = 6$
$$4 %3bool-xor%* 6 = 2$
.end
Here %3bool-xor%* is the exclusive or operation.
In general we will use terminology obtained by prefixing %3bool-%* to
the usual name of the corresponding logical operation for a boolean
operation.
The internal form for boolean operations on words has
not been standardized, but the form used by MACLISP is
.begin center
($BOOLE <code> <n1> <n2>)
.end
where <code> ranges from $0 to $15 (decimal) and each value of <code>
corresponds to a different boolean operation.
We have the following simple rule for determining what operation
corresponds to a particular value of <code>. If the binary
representation of <code> is "$$abcd$" then result of the operation
on a pair of bits $x and $y is given in table {table boolcode}.
.begin nofill select 6 turnon "∂" group
.x←24;y←28;xy←36
∂(x)x∂(y)y ∂(xy)(BOOLE "abcd" x y)
∂(x)0∂(y)0 ∂(xy+10)a
∂(x)0∂(y)1 ∂(xy+10)c
∂(x)1∂(y)0 ∂(xy+10)b
∂(x)1∂(y)1 ∂(xy+10)d
!tableboolcode Boolean operation encoding.!
.end
In particular if <code> is $0 we have the identically $0 operation,
if <code> is $15 we have the identically $1 operation,
if <code> is $1 we have %3bool-and%*,
and if <code> is $7 we have %3bool-or%*.
Note that all 16 boolean functions of two variables are realized
by the LISP $BOOLE operation.
In addition to the above operations LISP has a shift operation
⊗lsh[n,d] which shifts the bits of the binary representation of
⊗n, ⊗d positions to the left, filling the vacated spaces with zeroes. If
⊗d is negative the shifting is to the right instead. The internal form
of this operation is ($$LSH$_<n>_<d>).
Boolean operations are particularly useful when you have a problem
involving data that can easily be represented by bit strings or vectors.
Using the Boolean operations is very much more efficient than representing
the same data as lists of $$0$s and $$1$s, both in terms of space required
and in terms of computation time. It does not necessarily make the problem
or the programs easier to understand, however. We will see an example
of a problem solved using both list and bit represtations in Chapter
{SECTION SEARCH}.
.item←0
.cb Exercises
#. What boolean operation does $BOOLE perform when <code>=$11 (decimal)?
#. What <code> corresponds to the operation $$x=y$ ?
.ss(lambda,Lambda expressions and functions with functions as arguments.)
. <<eqn labels ae>>
It is common to use phrases like "the function ⊗⊗2x+y⊗". This
is not a precise notation because we cannot say ⊗⊗[2x+y][3,_4]⊗ and know
whether the desired result is 2%8*%*3+4 or 2%8*%*4+3 regarding the
expression as a function of two variables. Worse yet, we might have
meant a one-variable function of ⊗x wherein ⊗y is regarded as a
parameter.
Church's λ-notation provides a convenient way of giving names
to functions. In the above example, we would write
⊗⊗λx_y:_2x+y⊗ to denote the function of two variables with first
argument ⊗x and second argument ⊗y whose value is given by the
expression ⊗⊗2x+y⊗. Thus, ⊗⊗[λx_y:_2x+y][3,_4]_=_10⊗ and
_⊗⊗[λy_x:_2x+y][3,_4]=_11.⊗
Like variables of integration
and the bound variables of quantifiers in logic, variables following
the _λ_ are bound or dummy and may be replaced by any others
provided the replacement is done consistently throughout the
expression and does not
make any variable bound by _λ_ the same as a free variable in the
expression. Thus ⊗⊗λx_y:_2x+y⊗ represents the same function as
⊗⊗λy_x:_2y+x⊗ or ⊗⊗λu_v:_2u+v⊗ , but in the function of one argument
⊗⊗λx:_2x+y⊗, we cannot replace the variable ⊗x by ⊗y, though we could
replace it by ⊗u.
λ-notation plays two important roles in LISP. First, it
allows us to rewrite an expression containing two or more occurrences
of the same sub-expression in such a way that the expression occurs
only once. Thus ⊗⊗(2x+1)%54%*+3(2x+1)%53⊗ can be written
⊗⊗[λw:_w%54%*+3w%53%*][2x+1]⊗. This can save considerable
computation, and
corresponds to the practice in sequential programming of assigning to a
variable the value of a sub-expression that occurs more than once in
an expression and then writing the expression in terms of the
variable. It is sometimes called λ-binding.
The second use of λ-expressions is in using functions that
take functions as arguments. Suppose we want to form a new list from
an old one by applying a function ⊗f to each element of the list.
This can be done using the function ⊗mapcar defined by
!fcnmapcar& ⊗⊗⊗mapcar[f, u] ← qif qn u qthen qNIL qelse f[qa u] . mapcar[f, qd u]⊗.
Such a function is called a ⊗functional since one (or more) of its arguments
is a function. ⊗mapcar maps a function and a list into a list.
Suppose the operation we want to perform is squaring, and we want to
apply it to the list $$(1_2_3_4_5_6_7)$. We have
⊗⊗⊗mapcar[λx: x%52%*, $$(1 2 3 4 5 6 7)$] = $$(1 4 9 16 25 36 49)$⊗.
[Some implementations of LISP allow mapping functions to take
an arbitrary number of lists as arguments. The number of lists is the
number of arguments expected by the functional argument and the mapping
terminates when the shortest list is exhausted. Some implementations
of LISP require the arguments in reverse order - functional argument
second.]
A more general operation than ⊗mapcar is ⊗maplist
in which the function is applied to the successive sublists of the
list rather than to the elements. ⊗maplist is defined by
!fcnmaplist& ⊗⊗⊗maplist[f, u] ← qif qn u qthen qNIL qelse f[u] . maplist[f, qd u]⊗.
As an application of ⊗maplist and ⊗mapcar with functional arguments, we
shall define a function for differentiating algebraic expressions
involving sums and products.
The syntax for such expressions was given in {eqn expr}.
Recall, $PLUS followed by a list of arguments denotes the sum of these
arguments and $TIMES followed by a list of arguments denotes their
product. The function ⊗⊗diff[e,_v]⊗ gives the partial derivative of
the expression ⊗e with respect to the variable ⊗v. We have
.begin nofill group turnon "∂"
.n←12
∂(n)⊗⊗diff[e, v] ← ⊗
∂(n+4)⊗⊗qif qat e qthen [qif e = v qthen 1 qelse 0]⊗
∂(n+4)⊗⊗qelse qif qa e = $$PLUS$ qthen $$PLUS$ . mapcar[[λx: diff[x, v]], qd e]⊗
∂(n+4)⊗⊗qelse qif qa e = $$TIMES$ qthen ⊗
!fcndiff& ∂(n+6)⊗⊗$$PLUS$⊗
∂(n+6)⊗⊗. maplist[⊗
∂(n+8)⊗⊗[λx: $$TIMES$⊗
∂(n+13)⊗⊗. maplist[⊗
∂(n+17)⊗⊗[λy: qif x = y qthen diff[qa y, v] qelse qa y], qd e]], ⊗
∂(n+8)⊗⊗qd e]⊗
.end
The term that describes the rule for differentiating products
corresponds to the rule
⊗⊗⊗∂/∂v[%8P%*%4i%* e%4i%*] = %8S%*%4i%*%8 P%*%4j%* [qif i=j qthen ∂e%4j%*/∂v qelse e%4j%*] .⊗
and ⊗maplist has to be used rather than ⊗mapcar since whether to
differentiate in forming the product is determined by equality of the
indices ⊗i and ⊗j rather than equality of the terms ⊗⊗e%4i⊗ and
⊗⊗e%4j⊗.
The internal form for a λ-expression is
.once center
($LAMBDA <list of variables> <expression to be evaluated>).
Thus ⊗⊗λx: diff[x,v]⊗ is written $$(LAMBDA (X) (DIFF X V))$.
The internal form of of ⊗diff is given below.
Notice that the function arguments to ⊗maplist and ⊗mapcar have the form
.once center
($FUNCTION <λ-expression>).
This is necessary if the definition is to be compiled as the compiler must
recognize the fact that the following code must be compiled as a function.
If the definition is only to be interpreted then $FUNCTION
has the same effect as $QUOTE and in fact you may use $QUOTE
instead of $FUNCTION in definitions that will only be interpreted by MACLISP.
.begin nofill group select 6
(DEFUN DIFF (E V)
(COND ((ATOM E) (COND ((EQ E V) 1) (T 0)))
((EQ (CAR E) 'PLUS)
(CONS 'PLUS
(MAPCAR (FUNCTION (LAMBDA (X) (DIFF X V))) (CDR E))))
((EQ (CAR E) 'TIMES)
(CONS 'PLUS
(MAPLIST (FUNCTION
(LAMBDA (X)
(CONS 'TIMES
(MAPLIST (FUNCTION
(LAMBDA (Y)
(COND ((EQ X Y) (DIFF (CAR Y) V))
(T (CAR Y)))))
(CDR E)))))
(CDR E))))))
.end
The above paragraphing (known as "pretty printing") makes function
definitions easier to read because items beginning in the same column are
at the same parenthetical level.
Two additional useful functions with functions as arguments are the
predicates__⊗andlis _and__⊗orlis _defined by the equations
.begin nofill group
!fcnandlis& ⊗⊗⊗andlis[p, u] ← qn u qor [p[qa u] qand andlis[p, qd u]]⊗
!fcnorlis& ⊗⊗⊗ orlis[p, u] ← qnot qn u qand [p[qa u] qor orlis[p, qd u]]⊗.
.end
Another way of writing function definitions in internal notation
uses $LAMBDA to make a function of the right side of a definition.
It is like writing ⊗subst and ⊗alt as
.begin nofill group
⊗⊗⊗subst ← λx y z:[qif qat z qthen [qif z qeq y qthen x qelse z]
qelse subst[x,y,qa z] . subst[x,y,qd z]]⊗
⊗⊗⊗alt ← λu.[qif qn u qor qn qd u qthen u qelse qa u . alt qdd u]⊗.
.end
Internally these definitions of ⊗subst and ⊗alt take the forms
.begin select 6 nofill group indent 6,6
(DEFPROP SUBST
(LAMBDA (X Y Z)
(COND ((ATOM Z) (COND ((EQ Z X) Y) (T Z)))
(T (CONS (SUBST X Y (CAR Z)) (SUBST X Y (CDR Z))))))
EXPR)
.apart
.group
(DEFPROP ALT
(LAMBDA (U) (COND ((OR (NULL U) (NULL (CDR U))) U)
(T (CONS (CAR U) (ALT (CDDR U))))))
EXPR).
.end
The general form for this manner of writing functon definitions is
.once center
($DEFPROP <function name> <defining λ-expression> $EXPR)
and it is often used by programs that output LISP. It is a special case
of an operation on property lists. It puts the λ-expression on the $EXPR property
of the function name (which is an atom).
$EXPR says that the item is a LISP function defined
by an S-expression. (Rather than by a machine language subroutine, for instance).
The $DEFUN form of function definition has the same effect in that it forms
a λ-expression out of the list of variables and the right hand side
and puts it on the $EXPR property of the function name.
.SKIP
.item←0
.cb Exercises
#. Compute ⊗⊗diff[$$(TIMES X (PLUS Y 1) 3), X$]⊗ using the above
definition of ⊗diff. Now do you see why algebraic simplification is
important?
#. Compute ⊗⊗orlis[qqat, $$((A B) (C D) E)$]⊗.
#. Evaluate the S-expression
$$((LAMBDA (X) (LIST X (LIST (QUOTE QUOTE) X))) (QUOTE (LAMBDA (X)
(LIST X (LIST (QUOTE QUOTE) X)))))$
and say what its interesting property is. Variants of this expression
have important theoretical properties.
.ss(alpha,Label.)
.<<eqn labels af>>
The λ mechanism is not adequate for providing names for
recursive functions, because in this case there has to be a way of
referring to the function name within the function. Therefore, we
use the notation__⊗⊗label[f,_e]⊗__to denote the expression ⊗e but where
occurrences of ⊗f within ⊗e refer to the whole expression. For
example, suppose we wished to define a function that takes alternate
elements of each element of a list and makes a list of these. Thus,
we want
⊗⊗⊗altlis[$$((A B C) (A B C D) (X Y Z))$] = $$((A C) (A C) (X Z))$⊗.
We can make the definition
!fcnaltlis& ⊗⊗⊗altlis[u] ← mapcar[label[alt, λu: qif qn u qor qn qd u qthen u
qelse qa u . alt[qdd u]], u]⊗.
in internal form this would be written
.begin nofill select 6 group indent 6,6
(DEFUN ALTLIS (X)
(MAPCAR (QUOTE (LABEL ALT
(LAMBDA (X)
(COND (OR (NULL X) (NULL (CDR X))) X)
(T (CONS (CAR X) (ALT (CDDR X)))))))
X)).
.end
The general internal form of the label construct is
.once center
($LABEL <name> <function expression>),
The identifier ⊗alt in the above example is bound by ⊗label and
is local to that expression, and this is the general rule. The
label construct is not often used in LISP since it is more usual
to give functions global definitions.
.if false then begin "hide Park comment"
D. M. R. Park pointed out that
if we allow variables to represent functions and use a suitable λ
construction, the use of label could be avoided.
.end "hide Park comment"
.ss(evaluator,The function ⊗eval. )
⊗eval plays both a theoretical and a practical role in LISP.
Historically, the list notation for LISP functions and ⊗eval were first
devised in order to show how easy it is to define a universal function in LISP -
the idea was to advocate LISP as an alternative to Turing machines for doing
the elementary theory of computability. This role will be discussed in a later
chapter. S. R. Russell noted that
⊗eval could serve as an interpreter for LISP and promptly programmed it
in machine language with minor modifications to make it more practical.
An interpreter based on ⊗eval has remained a feature of most LISP systems.
Thus when you talking to LISP the system is in a loop that ⊗⊗read⊗s what you
type, ⊗⊗eval⊗s it and ⊗⊗print⊗s the result. [Of course a real LISP system
does many other things too, such a storage management, error handling,
etc.]
⊗eval for LISP expressions is analogous to the
interpreter ⊗numval for arithmetic expressions given in {eqn numval}.
The first argument to ⊗eval is a LISP expression
in internal notation. The second argument is an association list that
tells ⊗eval what value each variable has, and what function definition
is to be associated with each function name. Thus the association list is
a list of pairs where each pair consists either of a variable and the S-expression
corresponding to its value, or a function name and the S-expression
representing the function expression defining the function.
(Here a function expression is either a function name, or a lambda expression.)
The result of applying ⊗eval is the value of the term represented by the
S-expression in an
environment where the free variables are assigned the values given by
the association list and where the function names occuring free (i.e. not
bound in a label expression) denote functions defined by the associated
expressions in the association list.
Since any computation can be described as evaluating an expression
without free variables or function names, the second argument theoretically
plays a role mainly in the recursive definition of ⊗eval. Thus
we usually start our computations with the second argument qNIL.
To illustrate this, suppose we want to apply the function ⊗alt
to the list $$(A B C D E)$, i.e. we wish to evaluate ⊗⊗alt[$$(A B C D E)$]⊗.
This can be obtained by computing
.BEGIN NOFILL
⊗⊗eval[⊗$$((LABEL ALT$
$$(LAMBDA (X) (COND ((OR (NULL X) (NULL (CDR X))) X)$
$$(T (CONS (CAR X) (ALT (CDDR X)))))))$
$$(QUOTE (A B C D E)))$,
⊗⊗qNIL]⊗,
.END
which gives the expected result $$(A C E)$.
This manner of evaluating requires that auxiliary functions
must be defined within any expression where they are used (by using the
label construct) and worse yet, they must be defined separately for separate
occurrences. This can become very cumbersome and also makes expressions
fairly difficult to understand. Another approach is to use an association
list which associates each function name appearing in the expression
with the appropriate defining expression. Thus we could evaluate
⊗⊗alt[$$(A_B_C_D_E)$]⊗ by computing
.BEGIN NOFILL group select 2
eval[$$(ALT (QUOTE (A B C D E)))$,
$$((ALT LAMBDA (X) (COND ((OR (NULL X) (NULL (CDR X))) X)$
$$(T (CONS (CAR X) (ALT (CDDR X)))))))$].
.END
A simplified version of the usual LISP ⊗eval is the following:
.BEGIN NOFILL turnon "∂" group
.n←8
∂(n)⊗⊗eval[e, a] ←⊗
∂(n+4) ⊗⊗qif qat e qthen [qif numberp e qor e = qNIL qor e = qT qthen e
qelse qd assoc[e, a]]⊗
∂(n+4) ⊗⊗qelse qif qat qa e qthen⊗
∂(n+8) ⊗⊗[qif qa e = $QUOTE qthen qad e⊗
∂(n+8) ⊗⊗qelse qif qa e = $COND qthen evcond[qd e, a]⊗
∂(n+8) ⊗⊗qelse qif qa e = $LIST qthen evlist[qd e,a]⊗
∂(n+8) ⊗⊗qelse qif qa e = $CAR qthen qa eval[qad e, a]⊗
!fcneval&l ∂(n+8)⊗⊗qelse qif qa e = $CDR qthen qd eval[qad e, a]⊗
∂(n+8) ⊗⊗qelse qif qa e = $CONS qthen eval[qad e, a] . eval[qadd e, a]⊗
∂(n+8) ⊗⊗qelse qif qa e = $ATOM qthen qat eval[qad e, a]⊗
∂(n+8) ⊗⊗qelse qif qa e = $EQ qthen eval[qad e, a] qeq eval[qadd e, a]⊗
∂(n+8) ⊗⊗qelse eval[qd assoc[qa e, a] . qd e, a]]⊗
∂(n+4) ⊗⊗qelse qif qaa e = $LAMBDA qthen eval[qadda e, prup[qada e, evlist[qd e,a]] * a]⊗
∂(n+4) ⊗⊗qelse qif qaa e = $LABEL qthen eval[qadda e . qd e, [qada e . qadda e] . a]⊗,
.END
where the auxiliary functions ⊗evcond and ⊗evlist are defined by
!fcnevcond& ⊗⊗⊗evcond[u, a] ← qif eval[qaa u, a] qthen eval[qada u, a] qelse evcond[qd u, a]⊗,
!fcnevlist& ⊗⊗⊗evlist[u, a] ← qif qn u qthen qNIL qelse eval[qa u,a] . evlist[qd u, a]⊗,
and the auxiliary function ⊗prup, used for pairing up the elements of two
lists of equal length, is defined by
!fcnprup& ⊗⊗⊗prup[u, v] ← qif qn u qthen qNIL qelse [qa u . qa v] . prup[qd u,qd v]⊗.
Recall that ⊗assoc is defined by
!eqnassoc1 ⊗⊗⊗assoc[x,a] ← qif qn a qthen qNIL qelse qif qaa a qeq x qthen qa a qelse assoc[x,qd a].⊗
This simple ⊗eval expects that an expression is either a
constant (⊗number, qT, qNIL, or a $$QUOTE$d S-expression),
a variable whose value can be found on the association list,
a conditional expression, a list making
expression, or an application of a function, lambda expression
or label expression to a list of arguments. Thus ⊗eval checks to see
which of the above classes the expression to be evaluated falls into
and proceeds accordingly. If the expression, ⊗e, is atomic then it is either
a non $$QUOTE$d constant or a variable. If the former then ⊗eval just returns
the expression, if the latter it looks up the value on the association list, ⊗a.
If ⊗e is non-atomic but qa ⊗e is atomic then ⊗e is either
a $$QUOTE$d constant, a conditional, a list maker, or an application of a
function to a list of arguments. In the constant case the expression
being quoted (qad ⊗e) is returned. If ⊗e is a conditional then the list
of pairs is processed by the auxiliary evaluator ⊗evcond, which
⊗⊗eval⊗s the "if" parts (⊗⊗qaa u⊗) in order until a true one is found then
returns the result of ⊗⊗eval⊗ing the corresponding "then" part (⊗⊗qada u⊗).
In the list case the list of expressions to be evaluated
is given to ⊗evlist which returns a list of the values.
In the function application case there are two
possibilities. If the function to be applied
is one of the elementary functions, the indicated operation is performed
on the result of evaluating the arguments. Otherwise the function must
be defined in ⊗a, so ⊗eval looks up the definition, replaces the function
name by the function definition in the expression and restarts the evaluation.
If neither ⊗e nor qa ⊗e are atomic then it must be a lambda or label
application. In the lambda case the argument list is given to ⊗evlist to
be evaluated, the values are then paired with the list of variables to be
bound by the lambda (qada ⊗e) using ⊗prup and put on the front of ⊗a.
The body of the lambda (qadda ⊗e) is then evaluated using this new
association list. In the label case a new association list is formed by
pairing the function name (qada ⊗e) with the defining expression (qadda ⊗e)
and adding the result to the front of ⊗a. Then
the label expression is replaced in ⊗e by the defining expression and
this is evaluated using the new association list.
If ⊗e is not an expression of the sort expected by ⊗eval, then
the result is not defined. It would not be difficult to add additional
clauses to ⊗eval so that it would return reasonable error messages rather
than just being undefined (or dying in some strange way as would be
likely in an actual computer). It would be necessary to be make the
error messages distinguishable from legitimate values of the expression
so that errors at inner levels of evaluation could be passed up the chain.
This could be done by returning legitimate values as pairs whose first
element is one atom and error messages as pairs prefixed by another.
Terms containing ⊗eval would have to distinguish the cases.
Notice that
$COND and $LIST considered as pseudo-functions behave differently
than ordinary functions in that both can take
an arbitrary number of arguments while functions defined by a lambda
expression have a fixed number of arguments determined by the variable list
occuring in the lambda expression. Also, the usual manner of evaluation
an application term is LISP is to evaluate all of the arguments then
apply the function. This will not work for $COND as the main reason for
a conditional is to be able to select a term to evaluate depending on
some set of conditions and not to evaluate other terms under those conditions.
The above version of ⊗eval does not handle the propositional
constructs qand, qor, and qnot. The effect of these constructs
can be obtained by appropriate use of the condtional, but simply
defining functions for qand and qor will not work as the evaluation
of a function application requires that all of the arguments of
of the function be evaluated before it is applied while the specification
of qand and qor require that only as many of the arguments be evaluated
as are required to determine the answer.
Another problem is that in most implementations
they are allowed to take an arbitrary number of arguments. Thus
we need to build them into ⊗eval for things to work properly.
We will see later that LISP systems provide alternate solutions to
this problem by providing a variety of modes of function application.
(These are known as $EXPR, $FEXPR and $$LEXPR$s.) Macros are also
used for this purpose and will be explained later. Arithmetic is
also missing from our ⊗eval. Adding these constructs is essentially
like combining ⊗eval with the earlier evaluator ⊗numval and adding
any additional primitive operations that are desired.
We note that ⊗eval can evaluate itself if it is given an
association list containing the pairs
$(EVAL_._λeval), $(EVCOND_._λevcond), $(EVLIST_._λevlist),
$(ASSOC_._λassoc), $(PRUP_._λprup), and $(APPEND_._λappend)
where $λ<function_name> stands for the internal form of the expression
defining the named function. Thus
⊗⊗⊗eval[$$(EVAL '(CAR '(A.B)) NIL)$,alist] = $$A$⊗
where ⊗alist is some association list containing the above mentioned pairs
(and no other definitions of those functions).
When you talk to LISP you do not explicitly tell the interpreter
what association list to use generally. This is because
the LISP associates with each atom a list of properties, among these
are the value, and/or the function definition associated with that
atom. The LISP interpreter typically
looks up variable values and function definitions on the corresponding
property lists. Thus, instead of making up an association list
with the appropriate variables and functions defined, the property
lists must first be primed by doing $$SETQ$s for giving variables
initial values and $$DEFUN$s (or $$DEFPROP$s) for any functions
that need to be defined. These features will be discussed in
more detail in Chapter {SECTION IMPURE}.
.cb Exercises.
.item←0
.skip 2
#. What is the value of
.begin nofill
⊗⊗eval[$$(LEFT (QUOTE (A . B)))$,⊗
⊗⊗______$$((LEFT LAMBDA (X) (COND ((ATOM X) X) (T (LEFT (CAR X))))))$]⊗?
.end
#. Translate the definition of ⊗eval given above into internal notation.
#. Go to your nearest LISP system, type in your answer to the second exercise
and use it to check your answer to the first exercise.
.if false then begin "hide eval exercises"
#. Modify ⊗eval to return reasonably informative error messages when it is
given a non-acceptable expression to evaluate.
#. Modify ⊗eval to accept the propositional constructs qand, qor, and qnot.
.end "hide eval exercises"